package tree;

import java.util.ArrayList;
import java.util.List;

/**
 * 538. 把二叉搜索树转换为累加树
 * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
 * 使每个节点 node的新值等于原树中大于或等于node.val的值之和。
 */
public class ConvertBSTToGreaterTree_538 {
    // 保存中序遍历的节点的值
    List<Integer> middle = new ArrayList<>();
    int index = 0;
    int sum = 0;

    // 更简单的方法，题中要求我们将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。
    // 我们只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，
    // 即可得到题目要求的累加树
    public TreeNode convertBST2(TreeNode root) {
        if (root != null) {
            convertBST2(root.right);
            sum += root.val;
            root.val = sum;
            convertBST2(root.left);
        }
        return root;
    }


    /**
     * 中序遍历BST得到的数组递增，因此可以先获取二叉树的节点值，再据此重建二叉树
     *
     * @param root
     * @return
     */
    public TreeNode convertBST(TreeNode root) {
        midTraversal(root);
        for (int i : middle) {
            sum += i;
        }

        buildTree(root);
        return root;
    }

    private void midTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        midTraversal(root.left);
        middle.add(root.val);
        midTraversal(root.right);
    }

    private void buildTree(TreeNode root) {
        if (root == null) {
            return;
        }
        buildTree(root.left);
        sum = (index == 0 ? sum : sum - middle.get(index - 1));
        root.val = sum;
        index++;
        buildTree(root.right);
    }
}
